RE (complexidade)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Disambig_grey.svg/20px-Disambig_grey.svg.png)
Em Teoria da Computabilidade e na Teoria da Complexidade Computacional, RE (recursivamente enumerável) é uma classe de problemas de decisão onde uma resposta "sim" pode ser verificada por uma máquina de Turing em uma quantidade finita de tempo.[1] Informalmente, isto significa que se a resposta é "sim", então existe algum procedimento que leva um tempo finito para determinar isso. Por outro lado, se a resposta é "não", a máquina poderá nunca parar. Equivalentemente, RE é uma classe de problemas de decisão para que uma máquina de Turing pode listar todas as instâncias "sim", uma por uma (isto é o que 'enumerável' significa).
Similarmente, co-RE é o conjunto de todas as linguagens que são complementos de uma linguagem em RE. De certo modo, co-RE contém linguagens em que a pertinência pode ser refutada em uma quantidade finita de tempo, mas provar a pertinência poderá levar uma eternidade.
Cada membro de RE é um recursivamente enumerável e, portanto, um conjunto diofantino.
Relações com outras classes
[editar | editar código-fonte]O conjunto das linguagens recursivas (R) é um subconjunto de ambas RE e co-RE.[2] De fato, é a intersecção dessas duas classes:
RE-completo
[editar | editar código-fonte]RE-completo é um conjunto de problemas de decisão que são completos para RE. De certo modo, estes são os mais "difíceis" problemas recursivamente enumeráveis. Todos esses problemas são não recursivos. Geralmente, nenhuma restrição é colocada sobre as reduções usadas exceto que elas sejam reduções por mapeamento.
Exemplos de problemas RE-completo:
- Problema da parada: Determinar se um programa para a partir de uma dada entrada ou se ele continuará rodando para sempre.
- Pelo Teorema de Rice, decidir a pertinência em qualquer subconjunto não-trivial do conjunto de funções recursivas é RE-hard. Isto será completo quando o conjunto for recursivamente enumerável.
- John Myhill (1955)[3] provou que todos os conjuntos criativos e produtivos são RE-completo.
- A uniformidade do problema da palavra para grupos ou semigrupos. [Na verdade, o problema da palavra para alguns grupos individuais é RE-completo.]
- Decidir a pertinência em uma gramática formal irrestrita geral. [Novamente,algumas gramáticas individuais têm problema de pertinência RE-completo.]
- O problema de validade para a lógica de primeira ordem.
- Problema da correspondência de Post: Dado um conjunto finito de palavras, determinas se existe uma palavra que pode ser formada em uma composição de palavras (permitindo repetição) em dois diferentes modos.
- Determinar se uma equação diofantina tem alguma solução inteira.
co-RE-completo
[editar | editar código-fonte]co-RE-completo é um conjunto de problemas de decisão que são completos para co-RE. De certo modo, estes são os complementos dos mais difíceis problemas recursivamente enumeráveis.
Exemplos de problemas co-RE-completo:
- O problema do dominó para o dominó de Wang.
- O problema da satisfabilidade para lógica de primeira ordem.
Ver também
[editar | editar código-fonte]Referências
- ↑ Predefinição:CZoo
- ↑ Predefinição:CZoo
- ↑ Myhill, John (1955), «Creative sets», Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 1: 97–108, MR 0071379, doi:10.1002/malq.19550010205.